package bfs

// https://leetcode-cn.com/problems/couples-holding-hands/
// 情侣握手
// 直接算法: 优先边上的凑对 、情侣本身坐叉了的，又是偶数位置的，直接交换
// 官方解答: 通过 有向无环图 来解答
// 先推出 当前情侣对 之间的依赖关系，比如 下面的例子，就是 a -> b, a -> c, b -> c（优先用序号小的指向大的）
// 这样可以算出 连通整个链路，只需要 2 步: a -> b -> c
// 时间复杂度: O(n) （因为同一个点 需要重复遍历的次数是有限的，最多2次）
// 推广: 现实生活中也可能存在这种链式依赖的情况，通过有向无环图，能够分析出问题核心的依赖，并解决（?）
// a1 b1 a2 c1 b2 c2
// 算法: bfs, 先把有向无环图 整个通过map 画出来，然后依次遍历，直到最后遍历完所有的节点
// 修正后的答案: 每一个图都必须连接上，而且初始开销都是1
func MinSwapsCouples(row []int) int {
	// 记录情侣的编号，以及有向无环图，/ 2 为编号
	coupleRelyMap := make(map[int][]int)
	maxCoupleNum := 0
	for index := 0; index < len(row); index += 2 {
		left := (row[index] + 2) / 2
		right := (row[index+1] + 2) / 2
		startPoint, endPoint := 0, 0
		switch {
		case left < right:
			startPoint = left
			endPoint = right
		case left > right:
			startPoint = right
			endPoint = left
		default:
			// 情侣已经坐在了一起，没有依赖关系
		}

		if 0 != startPoint {
			if nil == coupleRelyMap[startPoint] {
				coupleRelyMap[startPoint] = make([]int, 0)
			}
			// 同一个对象编号，最多只能同时依赖两个编号的对象
			needInsert := true
			for _, currentRelyPoint := range coupleRelyMap[startPoint] {
				if currentRelyPoint == endPoint {
					needInsert = false
					break
				}
			}
			if needInsert {
				coupleRelyMap[startPoint] = append(coupleRelyMap[startPoint], endPoint)
			}
		}

		// 记录最大的序号，作为所有需要遍历完成的节点
		if left > maxCoupleNum {
			maxCoupleNum = left
		}
		if right > maxCoupleNum {
			maxCoupleNum = right
		}
	}

	stepMap := make(map[int]int)
	for index := 1; index <= maxCoupleNum; index++ {
		bfsGraph(index, 0, stepMap, coupleRelyMap)
	}

	maxStep := 0
	for _, currentStep := range stepMap {
		if currentStep > maxStep {
			maxStep = currentStep
		}
	}

	return maxStep
}

// bfs 遍历整个图
func bfsGraph(index int, currentStep int, stepMap map[int]int, relyMap map[int][]int) int {
	// 剪枝: 如果不是起始位置，并且之前遍历过，并且当前需要的步骤数 又比之前的小，就直接退出
	// （开销更大的更优先，而且也不存在直接用更小开销能直接替换掉的情况，因为更小开销的话，也不会和其他点产生联系了）
	//（更小的开销意味着更直接的关联，不会产生长图）
	if 0 != currentStep && 0 != stepMap[index] && stepMap[index] >= currentStep+1 {
		return 0
	}
	if stepMap[index] < currentStep {
		stepMap[index] = currentStep
	}
	if nil == relyMap[index] {
		return 0
	}
	// TODO: 这里要改造成用栈来统计，不要用递归（递归最后无法区分哪个是哪个图）
	for _, currentEndPoint := range relyMap[index] {
		currentStep++
		bfsGraph(currentEndPoint, currentStep, stepMap, relyMap)
	}
	return currentStep
}
